package algorithms.sorting.impl;

import algorithms.sorting.ISort;

/**
 * 
 * @author Vikas Bahirwani
 */
public class MergeSort implements ISort{

	private int[] givenArray;

	private void sortHelper(int lowerBound, int upperBound) {
		if(lowerBound>=upperBound){
			return;
		}
		
		int middle = (upperBound + lowerBound) / 2;

		sortHelper(lowerBound, middle);
		sortHelper(middle + 1, upperBound);
		merge(lowerBound, middle, upperBound);

	}

	private void merge(int lowerBound, int middle, int upperBound) {
		int x = lowerBound, y = middle + 1, z = 0;
		int[] helperArray = new int[upperBound - lowerBound + 1];

		for (; x <= middle && y <= upperBound; z++) {
			if (givenArray[x] < givenArray[y]) {
				helperArray[z] = givenArray[x];
				x++;
			} else {
				helperArray[z] = givenArray[y];
				y++;
			}
		}

		while (x <= middle) {
			helperArray[z] = givenArray[x];
			x++;
			z++;
		}
		while (y <= upperBound) {
			helperArray[z] = givenArray[y];
			y++;
			z++;
		}

		for (int i = lowerBound, j = 0; i <= upperBound; i++, j++) {

			givenArray[i] = helperArray[j];
		}

	}


	/* (non-Javadoc)
	 * @see algorithms.sorting.ISort#sort(int[])
	 */
	public int[] sort(int[] elements) {
		if (elements == null || elements.length <= 1) {
			return elements;
		}

		givenArray = elements;
		sortHelper(0, givenArray.length - 1);
		return givenArray;
	}

	public static void main(String[] args) {
		int a[] ={2,1,3,-4,-5,-1,7,60};
		
		MergeSort mergeSort = new MergeSort();
		int[] c = mergeSort.sort(a);
		for (int i : c) {
			
			System.out.println(i);
		}
		
	}
}
